package leetcode_500;

import java.util.ArrayList;

/**
 *@author 周杨
 *StrongPasswordChecker_420 判断一个字符串至少需要多少次操作能变成强字符串
 *describe:AC 100% 分析操作的优先级
 *see:https://www.cnblogs.com/zslhq/p/5986623.html
 *2018年7月27日 下午6:36:23
 */
public class StrongPasswordChecker_420 {
	 public int strongPasswordChecker(String s) {
         boolean hasDigit = false, hasLowercase = false, hasUppercase = false;
        
        char lastChar = ' ';
        int count = 1;
        ArrayList<Integer> repeatCounts = new ArrayList<Integer>();
        
        for(int i = 0; i < s.length(); i++){
            char tmpChar = s.charAt(i);
            
            //判断是否存在要求的字符
            if(tmpChar <= '9' && tmpChar >= '0')
                hasDigit = true;
            else if(tmpChar <= 'Z' && tmpChar >= 'A')
                hasUppercase = true;
            else if(tmpChar <= 'z' && tmpChar >= 'a')
                hasLowercase = true;
                
            //统计超过3连字符串的数量以及对应的个数
            if(lastChar == tmpChar){
                count++;
            }else{
                if(count >= 3)
                    repeatCounts.add(count);
                
                count = 1;
            }
            lastChar = tmpChar;
        }
        //循环结束后没有处理当前统计长度
        if(count >= 3)
            repeatCounts.add(count);
        
        //记录长度问题
        int lengthDifference = 0;
        if(s.length() > 20)
            lengthDifference = s.length() - 20;
        else
            lengthDifference = s.length() < 6 ? s.length() - 6 : 0;
            
        int steps = Math.abs(lengthDifference);
        
        int types = (hasDigit ? 0 : 1) + (hasUppercase ? 0 : 1) + (hasLowercase ? 0 : 1);
        
        //先满足长度要求
        if(lengthDifference < 0){
            while(lengthDifference != 0){
                lengthDifference++;
                types--;
                //本题中如果长度小，那么插入一个即可消除全部3连的
                repeatCounts.clear();   //这里偷懒了，如果字符串长度要求下限较大则应采用添加的方式进行处理，类同删除操作：条件稍微变化，N-1变为N-2
            }
        }else if(lengthDifference > 0){
            while(lengthDifference != 0){
                lengthDifference--;
                if(repeatCounts.size() != 0){
                    //删除操作 循环3次用于考虑先减哪种长度的连串
                    for(int i = 0; i < repeatCounts.size() * 3; i++){
                        int loc = i % repeatCounts.size();
                        if(repeatCounts.get(loc) % 3 == 0){
                            repeatCounts.set(loc, repeatCounts.get(loc) - 1);
                            break;
                        }
                        if(i >= repeatCounts.size() && repeatCounts.get(loc) % 3 == 1 && repeatCounts.get(loc) > 3){
                            repeatCounts.set(loc, repeatCounts.get(loc) - 1);
                            break;
                        }
                        if(i >= repeatCounts.size() * 2 && repeatCounts.get(loc) > 3){
                            repeatCounts.set(loc, repeatCounts.get(loc) - 1);
                            break;
                        }
                    }
                }
            }
        }
        
        //长度满足要求考虑种类要求
        while(types > 0){
            if(repeatCounts.size() != 0){
                for(int i = 0; i < repeatCounts.size(); i++){
                    if(repeatCounts.get(i) >= 3){
                        repeatCounts.set(i, repeatCounts.get(i) - 3);
                        break;
                    }
                }
            }
            types--;
            steps++;
        }
        
        for(int i = 0; i < repeatCounts.size(); i++){
            steps += repeatCounts.get(i) / 3;
        }
        
        return steps;
    }
}
